A computer program listing appendix containing the source code of a computer program that may be used with the present invention is incorporated herein by reference and appended hereto as one (1) original compact disk, and an identical copy thereof, containing a total of forty-one (41) files as follows:
1. Field of the Invention
The present invention relates generally to methods, computer programs and systems for automated signal analysis providing rapid and accurate detection, prediction, or quantification of changes in one or more signal features, characteristics, or properties as they occur. More particularly, the present invention relates to a method, computer program, or system for automated real-time signal analysis providing characterization of temporally-evolving densities and distributions of signal features of arbitrary-type signals in a moving time window by tracking output of order statistic filters (also known as percentile, quantile, or rank-order filters).
2. Description of the Prior Art
It is often desirable to detect and quantify feature changes in an evolving signal, and there have been numerous attempts to develop automated signal analysis means operable to do so. One well-known approach, for example, is based upon analysis of the signal""s mean value, which is typically a well known, well understood, and easily computed property. Other well-known techniques look for changes in signal variance or standard deviation over time.
Unfortunately, these commonly used approaches have significant drawbacks, including lack of robustness in the presence of signal outliers. Furthermore, in all but a few ideal cases, monitoring these individual parameters does not enable detection of all types of changes in feature distribution. This is because the mean and standard deviation rarely completely describe the signal distribution. Another problem that plagues many existing analysis techniques is that they are unable to deal adequately with real-world problems in which the analyzed signal is often highly complex, non-stationary, non-linear, and/or stochastic.
Another well-known approach, one more suited to practical situations than the above-mentioned methods, uses order statistics (e.g., the median or other percentile or quantile values). Order statistics are advantageous because they are directly related to the underlying distribution and are robust in the presence of outliers. For example, a method of signal analysis that enables the detection of state changes in the brain through automated analysis of recorded signal changes is disclosed in U.S. Pat. No. 5,995,868. This method addresses the problem of robustness in the presence of outliers through novel use of order-statistic filtering. Additionally, given information from a moving time window of a certain time scale, referred to as the xe2x80x9cforegroundxe2x80x9d, this method provides for real-time comparison thereof with a reference obtained from past data derived, e.g., from a longer time scale window, referred to as the xe2x80x9cbackground.xe2x80x9d This approach thereby addresses some of the normalization problems associated with complex, non-stationary signals.
Although the prior invention disclosed in U.S. Pat. No. 5,995,868 has successfully addressed many of the above-mentioned limitations, including normalization problems associated with complex non-stationary signals, it is lacking in breadth of scope. Detection of changes, for example, is limited to a particular order statistic of the signal. Additionally, the order statistic filter employed to detect signal changes requires large amounts of processing ability, memory, and power when used on digital signals for which sorting procedures are performed at each point in time. Furthermore, the method does not enable full analog implementation.
Most work on order statistic filters, such as median filters, and their implementation is in the areas of digital signal and image processing, which, as mentioned, requires large amounts of processing ability, memory, and power not practical or cost-effective for some applications. Work on analog median filters is limited to situations where the input is provided as parallel lines of data, and a program or circuit that implements the filter outputs a value that is equal to the median of the data on different input lines. Work on analog median filtering for continuous-time signals is not extensive, and no realizable implementations exist able to track a percentile (e.g., median) of a continuous-time signal. One reason for this is that the operation of finding the rank or order is non-linear, making modeling the procedure using an ordinary differential equation so complicated that it has not yet been addressed.
Due to the above-described and other problems, a need exists for a more general, powerful, and broad method for automated analysis of signals of any degree of complexity and type.
The present invention solves the above-described and other problems to provide a distinct advance in the art of automated signal analysis. More specifically, the present invention comprises a method, computer program, and system for real-time signal analysis providing characterization of temporally-evolving densities and distributions of signal features of arbitrary-type signals in a moving time window by tracking output of order statistic filters (also called percentile, quantile, or rank-order filters).
The present invention is operable to analyze input signals of arbitrary type, origin and scale, including, for example, continuous-time or discrete-time, analog or digital, scalar or multi-dimensional, deterministic or stochastic (i.e., containing a random component), stationary (i.e., time invariant) or non-stationary (i.e., time varying), linear or nonlinear. Thus, the present invention has broad applicability to analysis of many different types of complex signals and sequences of data, including but not limited to biological signals such as those produced by brain, heart, or muscle activity; physical signals such as seismic, oceanographic, or meteorological; financial signals such as prices of various financial instruments; communication signals such as recorded speech or video or network traffic signals; mechanical signals such as jet engine vibration; target tracking and recognition; signals describing population dynamics, ecosystems or bio-systems; signals derived from manufacturing or other queuing systems; chemical signals such as spectroscopic signals; and sequences of data such as word lists, documents, or gene sequences. Furthermore, the present invention is applicable to any set of signal features so long as they are quantifiable, thereby allowing for a high degree of system adaptability and selectivity.
Thus, the present invention enables automated detection and quantification of changes in the distribution of any set of quantifiable features of a raw input signal as they occur in time. The input signal, denoted as {x(t)}, can be any data parameterized by a real-valued variable, t, which will be interpreted as a time variable. The input signal may be optionally preprocessed in order to produce a new signal, the feature signal, denoted as {X(t)}. {X(t)} quantifies a set of features of the input signal that the system will use in detecting and quantifying changes. For a fixed t, X(t) is called the signal feature vector at time t. The feature vector has as many components as there are signal features. While potentially of substantial value, this preprocessing step is optional in the sense that the raw input signal itself may be used as the feature vector (i.e., X(t)=x(t)), in which case the invention proceeds to detect changes in the distribution of the raw input signal as it evolves in time. The desirability of preprocessing will depend upon the nature of the raw input signal and the nature of the features of interest.
The present invention also introduces a useful new object called the time-weighted feature density of a signal, {f(t,X)}, which can be computed from the feature signal at each point in time. This object allows access to estimates of the full time-dependent density and cumulative distribution function of varying signal features with any desired degree of accuracy, but confines these estimates to any desired time-scale through the use of time-weighting (time localization of feature density). This time-weighted feature density describes the raw input signal features measured in moving windows of time specified by the time-weight function, which allows a user to apply different significances to portions of available information (e.g., to consider recent information as more relevant than older information; or to weight information according to its reliability, etc.).
Moreover, the present invention allows for rapidly obtaining these estimates in a computationally efficient manner that can be implemented in digital or analog form, and a method for detecting, quantifying, and comparing changes of arbitrary type in the density/distribution of the feature vector as it changes. The significance of this increase in computational efficiency, along with analog implementability, becomes especially clear when considering medical device applications where, for example, the present invention enables currently used externally-worn devices that require daily battery recharging to become fully implantable devices with an operational lifetime of several years, thereby improving safety and convenience.
In operation, a raw time-varying input signal of arbitrary type, origin, and scale is received for analysis. Optionally, depending upon the nature of the raw input signal and the nature of the features of interest, pre-processing occurs to produce a feature signal more amenable to further analysis. Next, time-weighted density or distribution functions are determined for both a foreground or current time window portion of the signal and a background portion of the signal or reference signal (which also may be evolving with time, but potentially on a different timescale) in order to emphasize, as desired, certain data.
Percentile values for both foreground and background signals are then accurately estimated and compared so as to detect and quantify feature changes on any timescale and to any desired degree of precision as the raw input signal evolves in time. Density and distribution approximations may also be compared. As noted above, the state of the existing art requires that the data be laboriously sorted in order to determine these percentile values. In the present invention, however, percentile values are accurately estimated without sorting or stacking, thereby increasing processing speed and efficiency while reducing computation, memory, and power needs. Thus, the present invention is able to perform in a highly computationally efficient manner that can be implemented in a low power consumption apparatus consisting of an analog system, a digital processor, or a hybrid combination thereof, thereby providing tremendous system power savings.
The present invention is also operable to facilitate real-time signal normalization with respect to the density/distribution approximations, which is useful in processing and analysis of series of different orders. This is particularly useful where the features or characteristics of interest are invariant to a monotonic transformation of the signal""s amplitude.
It will also be appreciated that the present invention""s ability to rapidly and accurately detect changes in certain features of the input signal can enable prediction in cases where the changes it detects are associated with an increased likelihood of future signal changes. For example, when applied to seismic signals, the method can enable prediction of an earthquake or volcanic eruption; when applied to meteorological signals, the method can enable prediction of severe weather; when applied to financial data, the method can enable prediction of an impending price change in a stock; when applied to brain waves or heart signals, the method can enable prediction of an epileptic seizure or ventricular fibrillation; and when applied to brain wave or electromyographic signals, it can enable prediction of movement of a body part.
These and other novel features of the present invention are described in more detail below in the section titled DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT.